package day_7_6;

import java.util.ArrayList;
import java.util.List;

public class Main1 {
    /**
     * 131. 分割回文串
     * https://leetcode.cn/problems/palindrome-partitioning/description/?envType=study-plan-v2&envId=top-100-liked
     */
    private List<List<String>> ret = new ArrayList<>();
    private List<String> path = new ArrayList<>();
    int n;

    public List<List<String>> partition(String s) {
        n = s.length();
        dfs(0,s);
        return ret;
    }

    public void dfs(int pos,String s) {
        if(pos == n) {
            ret.add(new ArrayList<>(path));
            return;
        }

        for(int i = pos;i < n;i++) {
            if(isPalind(s,pos,i)) {
                // 判断是否是回文字符串，如果是，截取这一段的字符串，添加到 path 中，进行往后递归
                // 这个截取操作是 左闭右开 的
                path.add(s.substring(pos,i + 1));
                dfs(i + 1,s);
                // 回溯
                path.remove(path.size() - 1);
            }
        }
    }

    public boolean isPalind(String s,int left,int right) {
        while(left < right) {
            if(s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}
